package com.zjsru.plan2023.oneday.oneDay202301;

import java.util.Arrays;

/**
 * @Author: CookLee
 * @Date: 2023/1/9
 *
 * 还原排列的最少操作步数
 *  一步操作中，你将创建一个新数组 arr ，对于每个 i
 * 如果 i % 2 == 0 ，那么 arr[i] = perm[i / 2]
 * 如果 i % 2 == 1 ，那么 arr[i] = perm[n / 2 + (i - 1) / 2]、
 * 然后将 arr 赋值给 perm 。
 *
 *
 * 输入：n = 2
 * 输出：1
 * 解释：最初，perm = [0,1]
 * 第 1 步操作后，perm = [0,1]
 * 所以，仅需执行 1 步操作
 *
 * 输入：n = 4
 * 输出：2
 * 解释：最初，perm = [0,1,2,3]
 * 第 1 步操作后，perm = [0,2,1,3]
 * 第 2 步操作后，perm = [0,1,2,3]
 * 所以，仅需执行 2 步操作
 */
public class ReinitializePermutation {
    
    /**
     * 模拟
     */
    public int reinitializePermutation(int n) {
        //定义两个数组最后比较是否做到还原
        int[] perm = new int[n];
        int[] target = new int[n];
        for (int i = 0; i < n; i++) {
            perm[i] = i;
            target[i] = i;
        }
        //记录 执行的步长
        int step = 0;
        do {
            //定义数组arr 来作为变量
            int[] arr = new int[n];
            //一次完整的for循环算一步操作
            for (int i = 0; i < n; i++) {
                if (i % 2 == 0) {
                    arr[i] = perm[i / 2];
                }
                if (i % 2 == 1) {
                    arr[i] = perm[n / 2 + (i - 1) / 2];
                }
            }
            //赋值
            perm = arr;
            //没有还原成原来数组时，继续循环，并且步长+1
            step++;
        } while (!Arrays.equals(perm, target));
        return step;
    }
    
    public static void main(String[] args) {
        ReinitializePermutation reinitializePermutation = new ReinitializePermutation();
        int n = 2;
        System.out.println(reinitializePermutation.reinitializePermutation(n));
    }
}
